package com.lfg.leetcode.leetcode300;

import java.util.HashMap;
import java.util.Map;


public class No316removeDuplicateLetters {
    public static void main(String[] args) {
        String ret = removeDuplicateLetters("abacb");
        System.out.println("[" + ret + "]");
    }

    public static String removeDuplicateLetters(String s) {
        if (null == s) {
            return "";
        }
        int length = s.length();
        if (length == 0) {
            return "";
        }
        StringBuilder sb = new StringBuilder(length);
        Map<Character, Integer> data = new HashMap<>(length);
        for (int i = 0; i < length; i++) {
            data.put(s.charAt(i), i);
        }
        int index = 0;
        Character last = s.charAt(0);
        for (int i = 0; i < length; i++) {
            Character c = s.charAt(i);
            Integer pos = data.get(c);
            if (null == pos) {
                continue;
            }
            if (last == null) {
                last = c;
                index = i;
            }
            if (last > c) {
                last = c;
                index = i;
            }
            if (pos == i) {
                sb.append(last);
                data.remove(last);
                last = null;
                i = index;
            }
        }
        return sb.toString();
    }


}
